The present invention relates generally to network communications. More specifically, the present invention is a method and apparatus for using ranking to select repair nodes in formation of a dynamic tree for multicast repair
Internet Protocol (IP) multicasting is useful for disseminating data to a large group of receivers in a network. Multicast is a form of network communication in which a transmitting node, or sender, sends a single message to multiple destinations at once. The multiple destinations are the recipients, or receivers of the message. Other methods of network communication include broadcast, in which a sender transmits to all possible recipients, and unicast, in which the sender transmits only to one specific recipient. Multicast is described in more detail in D. Comer, Internetworking with TCP/IP, Prentice Hall, 1991, Chapter 17, which is herein incorporated by reference to the extent that it is not inconsistent with the present invention.
A multicast sender node sends a message to a multicast address. The sender transmits the message to any receivers that are listening for messages at the same multicast address. A set of receivers listening for messages at a particular multicast address are associated with the sender and form a multicast group in which the receivers are group members.
As the number of receivers joining a multicast group becomes large, the sender becomes overworked and slows down as a result of having to process notifications of receipt and requests for multicast repair from group members (receivers). Multicast repair is the process of the sender resending a multicast message in response to a request for retransmission (a xe2x80x9crepairxe2x80x9d request) from a receiver. The increased network traffic may cause a loss of data messages due to errors and overloading in the networking equipment.
In an embodiment consistent with the present invention, the sender sets up a hierarchical tree structure containing a plurality of receivers in which the sender is the root of the tree. The branches of the tree are repair groups. A repair group is a subset of the multicast group. The sender is the head of a first repair group. Each repair group contains a head and at least one receiver.
Each receiver has a ranking value corresponding to its ability to perform the duties of a head. Except for the sender, each of the heads are receivers which have a high enough ranking value to perform the duties of a head. If this ranking value is high enough, the receiver becomes a head and starts advertising for new members by sending multicast control messages containing the head""s ranking value.
A receiver collects advertisement messages from heads which are available (for example, heads which are nearby). The receiver uses the ranking values in these advertisements to rank the heads, and then picks the most suitable head based on the ranking. The receiver then responds to the advertisement messages by sending a join request message to the head it picked. If the head rejects the receiver""s membership request, the receiver sends a join request to the next most suitable head, i.e., the next highest ranked head. As some of the receivers become heads and other receivers become associated with those heads by joining groups, a hierarchical tree structure forms.
A receiver""s ranking value can fall within at least three value ranges: (1) xe2x80x9cunablexe2x80x9d to serve as a head, (2) xe2x80x9cablexe2x80x9d to serve as a head, and (3) xe2x80x9cwillingxe2x80x9d to serve as a head. xe2x80x9cWillingxe2x80x9d to serve as a head indicates that the receiver is a very good head candidate, thus ranking it higher than a head which is xe2x80x9cablexe2x80x9d to serve. In an embodiment consistent with the present invention, the value ranges may be represented by a point range from zero to ten, where zero represents xe2x80x9cunablexe2x80x9d to serve as a head, 1-9 represent xe2x80x9cablexe2x80x9d to serve as a head, and 10 represents xe2x80x9cwillingxe2x80x9d to serve as a head. Additional ranking values may be added to provide greater ranking flexibility by creating multiple levels of heads. For example, a value of xe2x80x9creluctantxe2x80x9d may be added to indicate a receiver which is xe2x80x9cablexe2x80x9d to serve but does not have as much resource capacity to serve as a receiver which is xe2x80x9cwillingxe2x80x9d to serve.
The sender delegates multicast repair to the heads in the tree so that the sender provides multicast repair only to a subset of the total receivers in the multicast group. This reduces the sender""s workload and enables the sender to send messages to larger multicast groups. The sender transmits multicast messages to all of the receivers at the multicast group address at a data rate which is preconfigured or dynamically determined. Receivers that have joined a group and become associated with a head may request re-transmissions of the multicast message from their associated head.
In accordance with an embodiment consistent with the present invention, a method and apparatus for forming a multicast repair tree performed by a data processor includes the step of determining a ranking value associated with a potential head for each of a plurality of potential heads in a multicast group. A potential head sends advertisements containing its ranking value. A plurality of potential receivers receive the advertisements. A potential receiver prioritizes the ranking values from the potential heads and binds to the head having the highest ranking value, thereby forming a group of which the potential receiver is a receiver and the potential head is the head. The head may be the sender of the multicast message. There may be a plurality of heads. There may be two or more possible ranking values including xe2x80x9cablexe2x80x9d, xe2x80x9cunablexe2x80x9d, xe2x80x9cwillingxe2x80x9d, and xe2x80x9creluctantxe2x80x9d to perform the duties of a head.
In accordance with an embodiment consistent with the present invention, a method and apparatus for forming a multicast repair tree, performed by a data processor, comprises the steps of determining, for each of a plurality of potential heads, a ranking value associated with the potential head; advertising, by the potential heads to a plurality of potential receivers; prioritizing, by a potential receiver, the ranking values from the potential heads; and binding, by a potential receiver to the potential head having the highest ranking value, thereby forming a repair group of which the potential receiver is a member and the highest ranking potential head is the head. An embodiment consistent with the present invention may be implemented as a computer program product or as a computer data signal embodied in a carrier wave. In accordance with another embodiment consistent with the present invention, a method and apparatus for forming a multicast repair tree, performed by a data processor, comprises the steps of receiving a plurality of advertisements, each containing a ranking value, from the potential heads; prioritizing the ranking values from the potential heads; and binding to the potential head having the highest ranking value, thereby forming a group in which the highest ranking potential head is the head. An embodiment consistent with the present invention may be implemented as a computer program product or as a computer data signal embodied in a carrier wave. In accordance with an embodiment consistent with the present invention, a method and apparatus for forming a multicast repair tree, performed by a data processor programmed to be a potential head, comprising the steps of determining a ranking value associated with the potential head; advertising to a plurality of potential receivers in accordance with the ranking value; receiving a join message from a potential receiver; and adding the potential receiver to a group in accordance with a predetermined limit. An embodiment consistent with the present invention may be implemented as a computer program product or as a computer data signal embodied in a carrier wave.
Advantages of the invention will be set forth, in part, in the description that follows and in part, will be understood by those skilled in the art from the description or may be learned by practice of the invention. The advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims and equivalents.